# tablernd.R
# escolhe um valor aleatorio entre uma tabela de probabilidades
# discretas

rndtable <- function(v, p, cp)
{
	# calcula P(sair A | nao saiu nenhum dos anteriores)
	# logo:   uma vez que P(A e B) = P(A|B).P(B)
	# P(1) = random()
	# P(i) = random() / 1-P(i-1)

	i <- 1
	while(TRUE) {
		if(i == length(p))
			break
		pi <- p[i] / (1-cp[i])
		if(rbinom(1, 1, pi) == 1)
			break
		i <- i+1
	}
	v[i]
}

teste <- function()
{
	p <- c(0.2, 0.3, 0.4, 0.1)
	v <- 1:length(p)

	stopifnot(sum(p) == 1)
	cp <- c(0,cumsum(p))

	# simulacao para verificar eficacia do algoritmo

	freqs <- rep(0, length(v))
	for(n in 1:100000) {
		i <- rndtable(v, p, cp)
		freqs[i] <- freqs[i]+1
	}

	relfreqs <- freqs / sum(freqs)

	print(relfreqs)
}

